A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. A Bloom filter is provided as a bit array, with each bit set to 0 when the Bloom filter is empty. A plurality of different hash functions are provided, with each hash function mapping, or hashing some set element to one of the array positions with a uniform random distribution. To add an element of a set to the Bloom filter, the element is fed to each of the hash functions to get a plurality of corresponding array positions. Each of the array positions is set to 1. To determine whether an element is in the Bloom filer, the element is again fed to each of the hash functions to re-determine the array positions. If any of the bits at the array positions are equal to 0, the element is not in the set. If all of the bits in the array position are equal to 1, the element is in the set, although false positives are possible.
Private set intersection (PSI) can enable parties, such as a client and a server, to compute the intersection of elements included within their respective sets without disclosing any information about these elements. During this process, the client can learn the intersection of elements within the sets, whereas the server does not learn the intersection of elements within the sets. PSI has many applications and is therefore a fundamental building block for many search-based computing technologies, such as law enforcement systems that search forensic databases storing DNA profiles or supply chain management systems that involve individual parties with various roles. One approach for checking the intersection of elements within two sets is to use Bloom filters. One disadvantage of Bloom filters is confidentiality.